package com.c2b.algorithm.newcoder.dynamic_programming;

/**
 * <a href="https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=295&tqId=23255&ru=%2Fpractice%2F4bcf3081067a4d028f95acee3ddcd2b1&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj">斐波那契数列</a>
 * <p>大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。</p>
 * <p>
 * <pre>
 *         斐波那契数列是一个满足
 *              fib(x) = 1                  ,x=1,2时,
 *              fib(x) = fib(x-1)+fib(x-2)  ,x>2时
 *          的数列
 *     </pre>
 * </p>
 * 数据范围：1≤n≤40<br>
 * 要求：空间复杂度O(1)，时间复杂度O(n) ，本题也有时间复杂度O(logn) 的解法<br>
 *
 * @author c2b
 * @since 2023/3/15 10:06
 */
public class BM0062Fibonacci_S {


    /**
     * 非递归
     */
    public int Fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        //初始化两个变量 f(0) = 0、f(1) = 1.
        int a;  // f(i-2)
        int b = 0;  // f(i-1)
        int res = 1;
        for (int i = 2; i <= n; i++) {
            a = b;
            b = res;
            res = (a + b) % 1000000007;
        }
        return res;
    }

    /**
     * 递归
     */
    public int Fibonacci_Recursion(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return Fibonacci_Recursion(n - 1) + Fibonacci_Recursion(n - 2);
    }

    public static void main(String[] args) {
        BM0062Fibonacci_S bm0062Fibonacci_s = new BM0062Fibonacci_S();
        //for (int i = 1; i <= 40; i++) {
        //    System.out.println(bm0062Fibonacci_s.Fibonacci_Recursion(i));
        //}
        for (int i = 1; i <= 48; i++) {
            System.out.println(bm0062Fibonacci_s.Fibonacci(i));
        }
    }
}
